#include<iostream>
#include<queue>
#include<vector>
using namespace std;

// 定义一个小根堆
priority_queue<int, vector<int>, greater<int>> minpq;

// 定义一个大根堆
priority_queue<int> maxpq;

// 操作1:插入x
void addx(int x)
{
	// 若小根堆空
	if(minpq.empty())
	{
		minpq.push(x);
		return;
	}
	
	// 若x大于小根堆堆顶元素
	if(x>minpq.top())
		minpq.push(x); // 将x插入到小根堆中
	else
		maxpq.push(x); // 否则将x插入到大根堆中
	
	// 若小根堆元素个数较少
	while(minpq.size()<maxpq.size())
	{
		minpq.push(maxpq.top());
		maxpq.pop(); // 取出大根堆堆顶元素插入到小根堆中
	}
	
	// 若小根堆比大根堆至少多2个元素
	while(minpq.size()>maxpq.size()+1)
	{
		maxpq.push(minpq.top());
		minpq.pop(); // 取出小根堆的堆顶元素插入到大根堆中
	}
}

// 操作2:求中位数
double getmiddle()
{
	// 输入的总元素个数为奇数
	if (minpq.size()!=maxpq.size())
		return minpq.top();
	
	// 输入的总元素个数为偶数
	else
		return (minpq.top()+maxpq.top())/2.0;
}


void solve(vector<int>& v)
{
	int i=0,x;
	while(i < v.size())
	{
		// 添加数据
		if(v[i]==1)
		{
			i++;
			x=v[i];
			addx(x);
			printf("    输入整数: %d\n",x); 
		}
		
		// 求中位数
		else if(v[i]==2)
		{
			double mid=getmiddle();
			printf("中位数: %g\n",mid); 
		}
		i++;
	}
}
int main()
{
	vector<int> v={1,2,1,6,1,3,1,2,2,1,5,2};
	solve(v);
	return 0;
}
